package 数据结构;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 二叉排序树
 *
 * @author wxg
 */
public class BSTTree<E> {
    private Node<E> root = null;
    private int size = 0;
    private Comparator<E> compare;

    public BSTTree(Comparator<E> compare) {
        this.compare = compare;
    }

    public int size() {
        return size;
    }

    public void create(Object[] objects) {
        if (objects == null || objects.length <= 0)
            return;
        for (Object object : objects) {
            add((E) object);
        }
    }

    public E find(E ele) {
        Node<E> node = root;
        while (node != null) {
            if (node.value == ele)
                return ele;
            node = compare.compare(node.value, ele) > 0 ? node.left : node.right;
        }
        return null;
    }

    public void add(E ele) {
        add(ele, true);
    }

    public void add(E ele, boolean isNotRepeat) {
        if (ele == null)
            return;
        Node<E> node = new Node<>();
        node.value = ele;
        if (root == null) {
            root = node;
        } else {
            if (isNotRepeat) {
                if (find(ele) != null)
                    return;
            }
            Node<E> troot = root;
            Node<E> tnode = null;
            while (troot != null) {
                tnode = troot;
                troot = compare.compare(tnode.value, ele) > 0 ? tnode.left : tnode.right;
            }
            if (compare.compare(tnode.value, ele) > 0) {
                tnode.left = node;
            } else {
                tnode.right = node;
            }
        }
        size++;
    }

    public void remove(E ele) {
        if (root == null)
            new NullPointerException();
        Node<E> parent = root;
        Node<E> current = root;
        boolean isLeftChild = false;
        while (current.value != ele) {
            parent = current;
            if (compare.compare(current.value, ele) > 0) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
            if (current == null) {
                return;
            }
        }
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            }
            if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        } else if (current.right == null) {
            if (current == root) {
                root = current.left;
            }
            if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.right;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            }
            if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.right;
            }
        } else {
            Node<E> curr = current.right;
            Node<E> p = curr;
            while (curr.left != null) {
                p = curr;
                curr = curr.left;
            }
            if (isLeftChild) {
                parent.left = curr;
            } else {
                parent.right = curr;
            }
            curr.left = current.left;
            curr.right = current.right;
            p.left = null;
            p.right = null;
            current = curr;
        }
        size--;
    }

    private class Node<E> {
        E value;
        Node<E> left;
        Node<E> right;
    }

    public E min() {
        return findMinNode(root).value;
    }

    public E max() {
        return findMaxNode(root).value;
    }

    private Node<E> findMinNode(Node<E> node) {
        if (root == null)
            return null;
        if (node.left == null)
            return node;
        else return findMinNode(node.left);
    }

    private Node<E> findMaxNode(Node<E> node) {
        if (root == null)
            return null;
        if (node.right == null)
            return node;
        else return findMaxNode(node.right);
    }

    public List<E> getAll() {
        List<E> list = new ArrayList<>(this.size);
        each(root, list);
        return list;
    }

    private void each(Node<E> node, List<E> list) {
        if (node != null) {
            list.add(node.value);
            each(node.left, list);
            each(node.right, list);
        }
    }

    public boolean contains(E ele) {
        E e = find(ele);
        return e == null ? false : true;
    }
}
